1. Field of the Invention
The present invention generally relates to the art of computerized computation as applied to the control of a process such as real-time control of a robot or other autonomous agent. The present invention relates also to the art of computerized learning systems (which are usually characterized by the need to perform repeated computations on run-time data) and more specifically to a register machine learning method in which the information and/or the computer program(s) that constitute solutions to a problem are created, initialized, stored, altered and executed in native machine code by using a higher level programming language to produce an optimized solution through the direct application of learning algorithms to the information stored in the native machine code.
In a preferred form of the invention, a computerized computation system performs repeated computations on data that is not known until a computer user is running the system (xe2x80x9crun-timexe2x80x9d, and xe2x80x9crun-time dataxe2x80x9d) and more specifically creates, initializes, stores, alters and executes both the run-time data and the computer code necessary to execute the repeated computations (the xe2x80x9crelated codexe2x80x9d) in native machine code operating on a register machine.
2. Description of the Related Art
The use of an evolutionary method to evolve controller architectures has been reported previously in a number of variants. Robotic controllers have, for instance, been evolved using dynamic recurrent neural nets. Several experiments have also been performed where a controller program has been evolved directly through genetic programming.
Previous experiments with genetic programming and robotic control, however, have been performed with a simulated robot and a simulated environment. In such a set-up, the environment and the robot can be reset easily to an initial state in order to ensure that each individual in the population is judged starting from the same state. Apart from being practically infeasible for a real robot, this method could result in over-specialization and failure to evolve a behavior that can generalize to unseen environments and tasks. To overcome the latter problem noise is sometimes artificially added to the simulated environment.
Machine learning systems in general have been proposed in the art for the solution of problems such as classification, prediction of time-series data, symbolic regression, optimal control, etc. Examples of various machine learning systems are neural networks, fuzzy networks, genetic algorithms (including genetic programming and classifier systems), Evolutionary Strategies, Evolutionary Programming, ADATE program induction, cellular automata, Box Jenkins optimization, ARMA optimization and many others. Rather than applying a direct computational approach, these systems create one or more proposed solutions in the form of data and computer program entities, and iteratively alter the data and/or entities for the purpose of finding an optimal solution to a problem. One such approach is described in, for example, U.S. Pat. No. 4,935,877, entitled xe2x80x9cNON-LINEAR GENETIC ALGORITHMS FOR SOLVING PROBLEMSxe2x80x9d, issued Jun. 19, 1990 to John Koza.
The set of practically solvable problems is highly related to the efficiency of the algorithm and implementation. It is therefore important to minimize the overhead involved in executing any machine learning system.
Machine learning systems create learned solutions to problems. These solutions have two elements: (1) Elements that hold the information that is learned during the execution of the machine learning system (the xe2x80x9cLearned Elementsxe2x80x9d); and (2) Elements that are necessary to convert the Learned Elements into meaningful action or output by the computer (the xe2x80x9cConversion Elementsxe2x80x9d). Existing machine learning approaches other than the present invention can be classified into two categories in terms of how they store and execute both the Learned Elements and the Conversion Elements. Those two categories are compiler based systems and interpreted systems.
An interpreted system is written in a high level language such as LISP and both the Learned and Conversion Elements are held in data-like structures such as LISP lists, which are converted (xe2x80x9cinterpretedxe2x80x9d) into native machine code at run-time by an interpreter. The interpreter, itself, also contains Conversion Elements for such interpreted, systems. So for example, U.S. Pat. No. 4,935,877 uses, as its Learning Elements various high level LISP expressions, customized for the problem at hand, to represent, symbolically, a xe2x80x9ccomputer program.xe2x80x9d That is, a high level xe2x80x9cprogramxe2x80x9d structure symbolized by the LISP List, is itself the subject of learning in that system. In this system, the Learned Elements are represented as a hierarchical tree structure. This solution gives good flexibility and the ability to customize the language depending on the constraints of the problem at hand.
The principal disadvantage of this interpreting approach to machine learning is that the Learned Elements and many of the Conversion Elements are stored in high level, symbolic data-like structures. Computers can operate only by executing native machine code. Thus, interpreting machine learning systems learn by modifying high level symbolic representations (the Learned Elements) that are, ultimately, converted into machine code by the interpreter at run-time. The need to convert (interpret) the Learned Elements and some of the Conversion Elements into native machine code at run-time before any useful action or output may be had from a computer is very time consuming and involves a large amount of overhead in machine resources such as CPU time, RAM memory, and disk space. In effect, all of the Learned Elements and the Conversion Elements in the LISP List are treated as run-time data that must be accessed and converted to machine code before any useful action or output may be had. Simply put, interpreted systems are slow and use a lot of a computer system""s resources.
Other machine learning systems are written in high level compiled computer languages such a C, C++, Pascal and so forth. This is the xe2x80x9ccompiler basedxe2x80x9d approach to machine learning. Large amounts of the Conversion Elements in such systems are compiled before run-time into native machine code in such a compiler based approach. Because those compiled Conversion Elements are already in native machine code at run-time, there is no need to interpret these Conversion Elements at run-time. Using a compiler based approach instead of an interpreted approach usually results in a substantial speed-up of the execution of the machine learning system, often increasing the speed of learning by a factor of ten times. Examples of such compiler based systems are GPC by Walter Tackett (genetic programming), Lil-GP (genetic programming), and EvoC (evolutionary strategies).
The compiler based approach to machine learning, while faster than the interpreted approach, must still access run-time data that is stored in data structures held in RAM memory or in some other form of memory such as hard disk. The reason that run-time data structures must be accessed in compiler based machine learning systems (or any machine learning system other than the present invention) is that the process of learning involves initializing and then altering the Learned Elements at run-time.
For example, the weights in a neural network are Learned Elements for neural network applications. Compiler based neural network systems hold those weights in data structures such as arrays or linked lists. Similarly, compiler based genetic programming systems store symbolic representations of program structures (the Learned Elements in genetic programming) in RAM data structures such as arrays, linked lists or parse trees. In all compiler based machine learning systems, the already compiled Conversion Elements must repeatedly access the Learned Elements (weights or symbolic representations of program structures) from the data structures in RAM memory in order to execute and evaluate the Learned Elements and to modify the Learned Elements according to the learning algorithm that is being used to modify the Learned Elements during learning. Such repeated access is necessary before any meaningful output or action may be had from a computer based on the Learned Elements. Such repeated accesses to RAM data structures is time consuming and uses extensive amounts of RAM to hold the Learned Elements.
More generally, computing systems that perform repeated calculations on run-time data may also be categorized as compiler based systems or interpreted systems. They store access, alter and execute run-time data in a manner similar to the storage, access, alteration and execution of the Learned Elements in the systems described above and are subject to the same limitations of slow execution and system overhead as the systems described above. By the phrase, xe2x80x9crepeated calculations (or computations) on (or of) run-time data,xe2x80x9d this application means the execution of one or more instructions that must access one or more elements of run-time data (from data storage such as RAM or hard disk) more than once on the same values of the run-time data.
The present invention overcomes the drawbacks of the prior art by providing a computerized computation system for a process such as real-time control of a robot or other autonomous agent. The present system avoids over-specialization, and is effective in evolving a behavior that can generalize to unseen environments and tasks. In addition, the present system operates much faster than any comparable system which has been proposed heretofore.
In accordance with the invention, a very general form of representing and specifying an autonomous agent""s behavior is by using a computer language. The task of planning feasible actions is then reduced to an instance of automatic programming. In a preferred embodiment of the invention, an evolutionary technique called Genetic Programming (GP) is used to directly control a miniature robot.
Two embodiments of the invention are presented. The objective of the GP-system in the first approach is to evolve real-time obstacle avoiding behavior from sensorial data. This technique enables real time learning with a real robot using genetic programming.
A population of computer programs or other entities is evolved using the GP-system by allowing selected entities to control the robot for brief periods of time and evaluating the effectiveness or fitness of the entities. The more fit entities are bred using genetic operators such as crossover and mutation to produce offspring which replace the less fit entities. In accordance with the present invention, the learning is distributed or stored in the population of entities.
In the first embodiment, the learning time is limited by the response dynamics of the environment. To overcome this problem, the second embodiment learns from past experiences stored in memory. In this aspect of the invention, vectors including sensor inputs, control outputs and empirically derived fitnesses which are generated during the real-time control of the robot are stored and updated in a memory, and used as a training set for the GP-system.
In the second embodiment of the present process control system, a computer model is constituted by the most currently fit entity in the population. As opposed to a conventional control system in which an output is defined as a function of an input, the present computer model defines fitness as a function of inputs and outputs. A computing unit accesses the model with a set of inputs, and determines a set of outputs for which the fitness meets a predetermined criterion, normally the best fitness. The present system does not merely mechanically calculate an output in response to an input as in the prior art, but associates a sensory-motor (input-output) state with a fitness in a manner that might be termed xe2x80x9cfeelingxe2x80x9d.
In a preferred embodiment, the present invention utilizes the lowest level binary machine code as the xe2x80x9centitiesxe2x80x9d or individuals or solutions. Every individual is a piece of machine code that is called and manipulated by the genetic operators.
There is no intermediate language or interpreting part of the program. The machine code program segments are invoked with a standard C function call. Legal and valid C-functions are put together, at run time, directly in memory by the genetic algorithm. The present system can therefore be considered as a xe2x80x9ccompilingxe2x80x9d machine learning implementation.
The present system generates binary code directly from an example set, and there are no interpreting steps. The invention uses the real machine instead of a virtual machine, and any loss in flexibility will be well compensated for by increased efficiency.
More specifically, one or more machine code entities such as functions are created which represent (1) solutions to a problem or (2) code that will perform repeated calculations on xe2x80x9crun-time dataxe2x80x9d that is encapsulated into the machine code. These entities are directly executable by a computer. The programs are created and altered by a program in a higher level language such as xe2x80x9cCxe2x80x9d which is not directly executable, but requires translation into executable machine code through compilation, interpretation, translation, etc.
The entities are initially created as an integer array that can be altered by the program as data, and are executed by the program by recasting a pointer to the array as a function type. The entities are evaluated by executing them with training data (as defined elsewhere) as inputs, and calculating xe2x80x9cfitnessesxe2x80x9d based on a predetermined criterion or by recovering the output as the result of one of the repeated calculations on run-time data.
After one or more xe2x80x9cexecutions,xe2x80x9d the entities are then altered by recasting the pointer to the array as a data (e.g. integer) type. Or the original data pointer to the array may have been typecast earlier to a function pointer in a way that did not permanently change the type of the pointer. In that case, the original data pointer is used in its original form. This process is iteratively repeated until an end criterion is reached.
In the case of machine learning, the entities change in such a manner as to improve their fitness, and one entity is ultimately produced which represents an optimal solution to the problem. In the case of repeated calculations on run-time data, the entity permits very rapid calculations to be performed generating usable output from the run-time data.
Each entity includes a plurality of directly executable machine code instructions, a header, a footer, and a return instruction. The alteration process is controlled such that only valid instructions are produced. The headers, footers and return instructions are protected from alteration.
The system can be implemented on an integrated circuit chip, with the entities stored in high speed memory in a central processing unit.
The present invention overcomes the drawbacks of the prior art by eliminating all compiling, interpreting or other steps that are required to convert a high level programming language instruction such as a LISP S-expression into machine code prior to execution.
Experiments have demonstrated that the present approach can speed up the execution of a machine learning or a repeated calculation system by 1,000 times or more as compared to systems which provide potential solutions in the form of high level xe2x80x9cprogram expressions in the interpreted approach. The speedup is in excess of 60 times over the compiler based approach. This makes possible the practical solutions to problems which could not heretofore be solved due to excessive computation time. For example, a solution to a difficult problem can be produced by the present system in hours, whereas a comparable solution might take years using conventional techniques.
These and other features and advantages of the present invention will be apparent to those skilled in the art from the following detailed description, taken together with the accompanying drawings, in which like reference numerals refer to like parts.